import collections


class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        last_mod = 0
        p = 0
        prefix = collections.defaultdict(int)
        n = len(nums)
        for i in range(n):
            p = (p + nums[i]) % k
            if prefix[p]:
                return True
            prefix[last_mod] = 1
            last_mod = p
        return False


data = Solution()
nums = [23, 2, 6, 4, 7]
k = 6
print(data.checkSubarraySum(nums, k))
nums = [23, 2, 4, 6, 7]
k = 6
print(data.checkSubarraySum(nums, k))
nums = [23, 2, 6, 4, 7]
k = 13
print(data.checkSubarraySum(nums, k))
